home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-04 / gs24src.zip / GXPATH2.C < prev    next >
C/C++ Source or Header  |  1992-02-13  |  15KB  |  492 lines
  1. /* Copyright (C) 1989, 1990, 1991 Aladdin Enterprises.  All rights reserved.
  2.    Distributed by Free Software Foundation, Inc.
  3.  
  4. This file is part of Ghostscript.
  5.  
  6. Ghostscript is distributed in the hope that it will be useful, but
  7. WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
  8. to anyone for the consequences of using it or for whether it serves any
  9. particular purpose or works at all, unless he says so in writing.  Refer
  10. to the Ghostscript General Public License for full details.
  11.  
  12. Everyone is granted permission to copy, modify and redistribute
  13. Ghostscript, but only under the conditions described in the Ghostscript
  14. General Public License.  A copy of this license is supposed to have been
  15. given to you along with Ghostscript so you can know your rights and
  16. responsibilities.  It should be in a file named COPYING.  Among other
  17. things, the copyright notice and this notice must be preserved on all
  18. copies.  */
  19.  
  20. /* gxpath2.c */
  21. /* Path tracing procedures for Ghostscript library */
  22. #include "math_.h"
  23. #include "gx.h"
  24. #include "gserrors.h"
  25. #include "gxfixed.h"
  26. #include "gxarith.h"
  27. #include "gzpath.h"
  28.  
  29. /* Forward declarations */
  30. private int copy_path(P3(gx_path *, gx_path *, fixed));
  31. private int flatten_recur(P8(gx_path *,
  32.   fixed, fixed, fixed, fixed, fixed, fixed, fixed));
  33.  
  34. /* Read the current point of a path. */
  35. int
  36. gx_path_current_point(gx_path *ppath, gs_fixed_point *ppt)
  37. {    if ( !ppath->position_valid )
  38.       return_error(gs_error_nocurrentpoint);
  39.     /* Copying the coordinates individually */
  40.     /* is much faster on a PC, and almost as fast on other machines.... */
  41.     ppt->x = ppath->position.x, ppt->y = ppath->position.y;
  42.     return 0;
  43. }
  44.  
  45. /* Read the bounding box of a path. */
  46. int
  47. gx_path_bbox(gx_path *ppath, gs_fixed_rect *pbox)
  48. {    if ( ppath->first_subpath == 0 )
  49.        {    /* The path is empty, use the current point if any. */
  50.         gx_path_current_point(ppath, &pbox->p);
  51.         return gx_path_current_point(ppath, &pbox->q);
  52.        }
  53.     /* The stored bounding box may not be up to date. */
  54.     /* Correct it now if necessary. */
  55.     if ( ppath->box_last == ppath->current_subpath->last )
  56.        {    /* Box is up to date */
  57.         *pbox = ppath->bbox;
  58.        }
  59.     else
  60.        {    gs_fixed_rect box;
  61.         register segment *pseg = ppath->box_last;
  62.         if ( pseg == 0 )    /* box is uninitialized */
  63.            {    pseg = (segment *)ppath->first_subpath;
  64.             box.p.x = box.q.x = pseg->pt.x;
  65.             box.p.y = box.q.y = pseg->pt.y;
  66.            }
  67.         else
  68.            {    box = ppath->bbox;
  69.             pseg = pseg->next;
  70.            }
  71. /* Macro for adjusting the bounding box when adding a point */
  72. #define adjust_bbox(pt)\
  73.   if ( (pt).x < box.p.x ) box.p.x = (pt).x;\
  74.   else if ( (pt).x > box.q.x ) box.q.x = (pt).x;\
  75.   if ( (pt).y < box.p.y ) box.p.y = (pt).y;\
  76.   else if ( (pt).y > box.q.y ) box.q.y = (pt).y
  77.         while ( pseg )
  78.            {    switch ( pseg->type )
  79.                {
  80.             case s_curve:
  81. #define pcurve ((curve_segment *)pseg)
  82.                 adjust_bbox(pcurve->p1);
  83.                 adjust_bbox(pcurve->p2);
  84. #undef pcurve
  85.                 /* falls through */
  86.             default:
  87.                 adjust_bbox(pseg->pt);
  88.                }
  89.             pseg = pseg->next;
  90.            }
  91. #undef adjust_bbox
  92.         ppath->bbox = box;
  93.         ppath->box_last = ppath->current_subpath->last;
  94.         *pbox = box;
  95.        }
  96.     return 0;
  97. }
  98.  
  99. /* Test if a path has any curves. */
  100. int
  101. gx_path_has_curves(gx_path *ppath)
  102. {    return ppath->curve_count != 0;
  103. }
  104.  
  105. /* Test if a path has any segments. */
  106. int
  107. gx_path_is_void(gx_path *ppath)
  108. {    return ppath->first_subpath == 0;
  109. }
  110.  
  111. /* Test if a path is a rectangle. */
  112. /* If so, return its bounding box. */
  113. int
  114. gx_path_is_rectangle(gx_path *ppath, gs_fixed_rect *pbox)
  115. {    subpath *pseg0;
  116.     segment *pseg1, *pseg2, *pseg3, *pseg4;
  117.     if (    ppath->subpath_count == 1 &&
  118.         (pseg1 = (pseg0 = ppath->first_subpath)->next) != 0 &&
  119.         (pseg2 = pseg1->next) != 0 &&
  120.         (pseg3 = pseg2->next) != 0 &&
  121.         (pseg4 = pseg3->next) != 0 &&
  122.         pseg4->type == s_line_close &&
  123.         ppath->curve_count == 0
  124.        )
  125.        {    fixed x0 = pseg0->pt.x, y0 = pseg0->pt.y;
  126.         fixed x2 = pseg2->pt.x, y2 = pseg2->pt.y;
  127.         if (    (x0 == pseg1->pt.x && pseg1->pt.y == y2 &&
  128.              x2 == pseg3->pt.x && pseg3->pt.y == y0) ||
  129.             (x0 == pseg3->pt.x && pseg3->pt.y == y2 &&
  130.              x2 == pseg1->pt.x && pseg1->pt.y == y0)
  131.            )
  132.            {    /* Path is a rectangle.  Return bounding box. */
  133.             if ( x0 < x2 )
  134.                 pbox->p.x = x0, pbox->q.x = x2;
  135.             else
  136.                 pbox->p.x = x2, pbox->q.x = x0;
  137.             if ( y0 < y2 )
  138.                 pbox->p.y = y0, pbox->q.y = y2;
  139.             else
  140.                 pbox->p.y = y2, pbox->q.y = y0;
  141.             return 1;
  142.            }
  143.        }
  144.     return 0;
  145. }
  146.  
  147. /* Copy a path */
  148. int
  149. gx_path_copy(gx_path *ppath_old, gx_path *ppath)
  150. {    return copy_path(ppath_old, ppath, (fixed)0);
  151. }
  152.  
  153. /* Translate an already-constructed path (in device space). */
  154. /* Don't bother to translate the cbox. */
  155. int
  156. gx_path_translate(gx_path *ppath, fixed dx, fixed dy)
  157. {    segment *pseg;
  158. #define translate_xy(pt)\
  159.   pt.x += dx, pt.y += dy
  160.     translate_xy(ppath->bbox.p);
  161.     translate_xy(ppath->bbox.q);
  162.     translate_xy(ppath->position);
  163.     pseg = (segment *)(ppath->first_subpath);
  164.     while ( pseg )
  165.        {    switch ( pseg->type )
  166.            {
  167.         case s_curve:
  168.            {    curve_segment *pc = (curve_segment *)pseg;
  169.             translate_xy(pc->p1);
  170.             translate_xy(pc->p2);
  171.            }
  172.         default:
  173.             translate_xy(pseg->pt);
  174.            }
  175.         pseg = pseg->next;
  176.        }
  177.     return 0;
  178. }
  179.  
  180. /* Flatten a path */
  181. private fixed
  182. scale_flatness(floatp flatness)
  183. {    /* See the flattening algorithm below for an explanation of */
  184.     /* the following computation. */
  185.     fixed scaled_flat = float2fixed(flatness);
  186.     return (scaled_flat > int2fixed(100) ? int2fixed(100) :
  187.         scaled_flat <= float2fixed(0.2) ? float2fixed(0.2) :
  188.         scaled_flat);
  189. }
  190. int
  191. gx_path_flatten(gx_path *ppath_old, gx_path *ppath, floatp flatness)
  192. {    return copy_path(ppath_old, ppath, scale_flatness(flatness));
  193. }
  194.  
  195. /* Add a flattened curve to a path. */
  196. int
  197. gx_path_add_flattened_curve(gx_path *ppath,
  198.   fixed x1, fixed y1, fixed x2, fixed y2, fixed x3, fixed y3,
  199.   floatp flatness)
  200. {    return flatten_recur(ppath, x1, y1, x2, y2, x3, y3,
  201.                  scale_flatness(flatness));
  202. }
  203.  
  204. /* Copy a path, optionally flattening it. */
  205. /* If the copy fails, free the new path. */
  206. private int
  207. copy_path(gx_path *ppath_old, gx_path *ppath, fixed scaled_flat)
  208. {    gx_path old;
  209.     segment *pseg;
  210.     int code;
  211. #ifdef DEBUG
  212. if ( gs_debug['p'] )
  213.     gx_dump_path(ppath_old, "before copy_path");
  214. #endif
  215.     old = *ppath_old;
  216.     gx_path_init(ppath, &ppath_old->memory_procs);
  217.     pseg = (segment *)(old.first_subpath);
  218.     while ( pseg )
  219.        {    switch ( pseg->type )
  220.            {
  221.         case s_start:
  222.             code = gx_path_add_point(ppath, pseg->pt.x, pseg->pt.y);
  223.             break;
  224.         case s_curve:
  225.            {    curve_segment *pc = (curve_segment *)pseg;
  226.             if ( scaled_flat == 0 )    /* don't flatten */
  227.                 code = gx_path_add_curve(ppath,
  228.                     pc->p1.x, pc->p1.y,
  229.                     pc->p2.x, pc->p2.y,
  230.                     pc->pt.x, pc->pt.y);
  231.             else
  232.                 code = flatten_recur(ppath,
  233.                     pc->p1.x, pc->p1.y,
  234.                     pc->p2.x, pc->p2.y,
  235.                     pc->pt.x, pc->pt.y,
  236.                     scaled_flat);
  237.             break;
  238.            }
  239.         case s_line:
  240.             code = gx_path_add_line(ppath, pseg->pt.x, pseg->pt.y);
  241.             break;
  242.         case s_line_close:
  243.             code = gx_path_close_subpath(ppath);
  244.             break;
  245.            }
  246.         if ( code )
  247.            {    gx_path_release(ppath);
  248.             if ( ppath == ppath_old ) *ppath_old = old;
  249.             return code;
  250.            }
  251.         pseg = pseg->next;
  252.     }
  253.     ppath->position = old.position;        /* restore current point */
  254. #ifdef DEBUG
  255. if ( gs_debug['p'] )
  256.     gx_dump_path(ppath, "after copy_path");
  257. #endif
  258.     return 0;
  259. }
  260. /* Internal routine to flatten a curve. */
  261. /* This calls itself recursively, using binary subdivision, */
  262. /* until the approximation is good enough to satisfy the */
  263. /* flatness requirement.  The starting point is ppath->position, */
  264. /* which gets updated as line segments are added. */
  265.  
  266. /* Table of f(i) = 256 * sqrt(1 + (i/64)^2). */
  267. /* This is good to within 1% or better. */
  268. #define scaled_sqrt_shift 6        /* scaling of index */
  269. #define sqrt_scale_shift 8        /* scaling of value */
  270. private int scaled_sqrt_tab[65] =
  271.    {    256, 256, 256, 256, 256, 256, 257, 257,
  272.     257, 258, 259, 259, 260, 261, 262, 262,
  273.     263, 264, 265, 267, 268, 269, 270, 272,
  274.     273, 274, 276, 277, 279, 281, 282, 284,
  275.     286, 288, 289, 291, 293, 295, 297, 299,
  276.     301, 304, 306, 308, 310, 312, 315, 317,
  277.     320, 322, 324, 327, 329, 332, 334, 337,
  278.     340, 342, 345, 348, 350, 353, 356, 359,
  279.     362
  280.    };
  281. private int flatten_sample(P8(gx_path *, int,
  282.   fixed, fixed, fixed, fixed, fixed, fixed));
  283.  
  284. private int
  285. flatten_recur(gx_path *ppath,
  286.   fixed x1, fixed y1, fixed x2, fixed y2, fixed x3, fixed y3,
  287.   fixed scaled_flat)
  288. {    fixed
  289.       x0 = ppath->position.x,
  290.       y0 = ppath->position.y;
  291. top:
  292. #ifdef DEBUG
  293. if ( gs_debug['2'] )
  294.     dprintf4("[2]x0=%f y0=%f x1=%f y1=%f\n",
  295.          fixed2float(x0), fixed2float(y0),
  296.          fixed2float(x1), fixed2float(y1)),
  297.     dprintf4("   x2=%f y2=%f x3=%f y3=%f\n",
  298.          fixed2float(x2), fixed2float(y2),
  299.          fixed2float(x3), fixed2float(y3));
  300. #endif
  301.     /*
  302.      * Compute the maximum distance of the curve from
  303.      * the line (x0,y0)->(x3,y3).  We do this conservatively
  304.      * by observing that the curve is enclosed by the
  305.      * quadrilateral of its control points, so we simply
  306.      * compute the distances of (x1,y1) and (x2,y2)
  307.      * from the line.  Letting dx = x3-x0 and dy = y3-y0,
  308.      * the distance of (xp,yp) from the line is
  309.      * abs(N)/sqrt(D), where N = dy*(xp-x0)-dx*(yp-y0) and
  310.      * D = dx*dx+dy*dy; hence we want to test abs(N) <= sqrt(D)*F,
  311.      * where F is the flatness parameter from the graphics state.
  312.      * We can do this more efficiently by letting t=dy/dx, and
  313.      * testing abs(N1) <= sqrt(D1)*f, where N1=t*(xp-x0)-(yp-y0) and
  314.      * D1 = 1+t*t.  If dx < dy, we swap x and y for this
  315.      * computation.  This guarantees abs(t) <= 1, which allows us to
  316.      * compute sqrt(1+t*t) by table lookup on the high bits of abs(t).
  317.      */
  318.      { fixed dx3 = x3 - x0;
  319.        fixed adx3 = any_abs(dx3);
  320.        fixed dy3 = y3 - y0;
  321.        fixed ady3 = any_abs(dy3);
  322.        /* We have to be quite careful to ensure that */
  323.        /* none of the multiplications will overflow. */
  324. #define short_max 0x7ff0L
  325. #define reduce_3(ad3, maxv)\
  326.   while ( ad3 > maxv )\
  327.     adx3 >>= 1, ady3 >>= 1,\
  328.     dx3 = arith_rshift_1(dx3), dy3 = arith_rshift_1(dy3)
  329. #define reduce_d(d)\
  330.   for ( shift = 0; (d < 0 ? d < -short_max : d > short_max); shift++ )\
  331.     d = arith_rshift_1(d)
  332.        if ( adx3 > ady3 )
  333.         {    fixed d, dx, dy, dist;
  334.         int shift;
  335.         reduce_3(ady3, short_max);
  336.         d = (scaled_sqrt_tab[(ady3 << scaled_sqrt_shift) / adx3] * scaled_flat) >> sqrt_scale_shift;
  337.         dx = x1 - x0, dy = y1 - y0;
  338.         reduce_d(dx);
  339.         if ( ((dist = ((dx * dy3 / dx3) << shift) - dy) < 0 ?
  340.               -dist : dist) > d )
  341.           goto sub;    /* not flat enough */
  342.         dx = x2 - x0, dy = y2 - y0;
  343.         reduce_d(dx);
  344.         if ( ((dist = ((dx * dy3 / dx3) << shift) - dy) < 0 ?
  345.               -dist : dist) > d )
  346.           goto sub;    /* not flat enough */
  347.         }
  348.        else if ( ady3 != 0 )
  349.         {    fixed d, dy, dx, dist;
  350.         int shift;
  351.         reduce_3(adx3, short_max);
  352.         d = (scaled_sqrt_tab[(adx3 << scaled_sqrt_shift) / ady3] * scaled_flat) >> sqrt_scale_shift;
  353.         dy = y1 - y0, dx = x1 - x0;
  354.         reduce_d(dy);
  355.         if ( ((dist = ((dy * dx3 / dy3) << shift) - dx) < 0 ?
  356.               -dist : dist) > d )
  357.           goto sub;    /* not flat enough */
  358.         dy = y2 - y0, dx = x2 - x0;
  359.         reduce_d(dy);
  360.         if ( ((dist = ((dy * dx3 / dy3) << shift) - dx) < 0 ?
  361.               -dist : dist) > d )
  362.           goto sub;    /* not flat enough */
  363.         }
  364.        else                /* adx3 = ady3 = 0 */
  365.         {    /* (x0,y0) is the same point as (x3,y3). */
  366.         /* This is an anomalous case.  If the entire curve */
  367.         /* is a single point, stop now, otherwise subdivide. */
  368.         if ( x1 != x0 || y1 != y0 || x2 != x0 || y2 != y0 )
  369.           goto sub;
  370.         }
  371.      }
  372.     /* Curve is flat enough.  Add a line and exit. */
  373. #ifdef DEBUG
  374. if ( gs_debug['2'] )
  375.     dprintf2("[2]\t*** x=%f, y=%f ***\n",
  376.          fixed2float(x3), fixed2float(y3));
  377. #endif
  378.     return gx_path_add_line(ppath, x3, y3);
  379.  
  380.     /* Curve isn't flat enough.  Break into two pieces and recur. */
  381.     /* Algorithm is from "The Beta2-split: A special case of the */
  382.     /* Beta-spline Curve and Surface Representation," B. A. Barsky */
  383.     /* and A. D. DeRose, IEEE, 1985, courtesy of Crispin Goswell. */
  384. sub:
  385.     /* We have to define midpoint carefully to avoid overflow. */
  386.     /* (If it overflows, something really pathological is going on, */
  387.     /* but we could get infinite recursion that way.... */
  388. #define midpoint(a,b)\
  389.   (arith_rshift_1(a) + arith_rshift_1(b) + ((a) & (b) & 1))
  390.    {    fixed x01 = midpoint(x0, x1), y01 = midpoint(y0, y1);
  391.     fixed x12 = midpoint(x1, x2), y12 = midpoint(y1, y2);
  392.     fixed x02 = midpoint(x01, x12), y02 = midpoint(y01, y12);
  393.     int code;
  394.     /* Update x/y1, x/y2, and x/y0 now for the second half. */
  395.     x2 = midpoint(x2, x3), y2 = midpoint(y2, y3);
  396.     x1 = midpoint(x12, x2), y1 = midpoint(y12, y2);
  397.     code = flatten_recur(ppath, x01, y01, x02, y02,
  398.         (x0 = midpoint(x02, x1)), (y0 = midpoint(y02, y1)),
  399.         scaled_flat);
  400.     if ( code < 0 ) return code;
  401.    }    goto top;
  402. }
  403.  
  404. /* Flatten a segment of the path by repeated sampling. */
  405. /* For some reason, this produces better results, */
  406. /* even though flatten_recur is careful to check the flatness.... */
  407. /* n is the number of points to sample, including the endpoints; */
  408. /* we require n >= 3. */
  409. private int
  410. flatten_sample(gx_path *ppath, int n,
  411.   fixed x1, fixed y1, fixed x2, fixed y2, fixed x3, fixed y3)
  412. {    const fixed
  413.         x0 = ppath->position.x,
  414.         y0 = ppath->position.y;
  415.     const fixed
  416.         cx = 3 * (x1 - x0),
  417.         bx = 3 * (x2 - x1) - cx,
  418.         ax = x3 - bx - cx - x0;
  419.     const fixed
  420.         cy = 3 * (y1 - y0),
  421.         by = 3 * (y2 - y1) - cy,
  422.         ay = y3 - by - cy - y0;
  423.     const float
  424.         dt = 1.0 / (float)(n - 1);
  425.     int i;
  426.  
  427.     for ( i = 1; i < n-1; i++ )
  428.        {    const float t = dt * (float)(i);
  429.         const fixed x = x0 + (fixed)(t*(cx + t*(bx + t*ax)));
  430.         const fixed y = y0 + (fixed)(t*(cy + t*(by + t*ay)));
  431.         int code;
  432.         if ( 0 != (code = gx_path_add_line(ppath, x, y)) )
  433.             return code;
  434.        }
  435.     return gx_path_add_line(ppath, x3, y3);
  436. }
  437.  
  438. /* Reverse a path. */
  439. /* We know ppath != ppath_old. */
  440. int
  441. gx_path_reverse(gx_path *ppath_old, gx_path *ppath)
  442. {    subpath *psub = ppath_old->first_subpath;
  443. #ifdef DEBUG
  444. if ( gs_debug['p'] )
  445.     gx_dump_path(ppath_old, "before reversepath");
  446. #endif
  447.     gx_path_init(ppath, &ppath_old->memory_procs);
  448. nsp:    while ( psub )
  449.        {    segment *pseg = psub->last;
  450.         segment *prev;
  451.         int code = gx_path_add_point(ppath, pseg->pt.x, pseg->pt.y);
  452.         if ( code < 0 )
  453.            {    gx_path_release(ppath);
  454.             return code;
  455.            }
  456.         for ( ; ; pseg = prev )
  457.            {    prev = pseg->prev;
  458.             switch ( pseg->type )
  459.                {
  460.             case s_start:
  461.                 /* Finished subpath */
  462.                 if ( psub->closed )
  463.                     code = gx_path_close_subpath(ppath);
  464.                 psub = (subpath *)psub->last->next;
  465.                 goto nsp;
  466.             case s_curve:
  467.                {    curve_segment *pc = (curve_segment *)pseg;
  468.                 code = gx_path_add_curve(ppath,
  469.                     pc->p2.x, pc->p2.y,
  470.                     pc->p1.x, pc->p1.y,
  471.                     prev->pt.x, prev->pt.y);
  472.                 break;
  473.                }
  474.             case s_line:
  475.             case s_line_close:
  476.                 code = gx_path_add_line(ppath, prev->pt.x, prev->pt.y);
  477.                 break;
  478.                }
  479.             if ( code )
  480.                {    gx_path_release(ppath);
  481.                 return code;
  482.                }
  483.            }
  484.     }
  485.     ppath->position = ppath_old->position;        /* restore current point */
  486. #ifdef DEBUG
  487. if ( gs_debug['p'] )
  488.     gx_dump_path(ppath, "after reversepath");
  489. #endif
  490.     return 0;
  491. }
  492.